

#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;


struct TreeNode 
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) 
    {}
};

using Node = TreeNode;

class Solution
{
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if (!pRootOfTree)
            return nullptr;

        Node* prev = nullptr;

        _InOrder(pRootOfTree, prev);

        Node* mini = pRootOfTree;
        while (mini->left)
        {
            mini = mini->left;
        }

        return mini;
    }

    TreeNode* buildTree1(vector<int>& preorder, vector<int>& inorder)
    {
        int index = 0;

        return _buildTree1(preorder, inorder, index, 0, preorder.size() - 1);
    }

    vector<int> inorderTraversal(TreeNode* root)
    {
        if (!root)
            return {};

        vector<int> v;
        stack<Node*> st;
        v.reserve(100);

        Node* cur = root;
        while (cur || !st.empty())
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            v.push_back(st.top()->val);

            cur = st.top()->right;
            st.pop();
        }

        return v;
    }

    vector<int> postorderTraversal(TreeNode* root)
    {
        if (!root)
            return {};

        stack<Node*> st;
        vector<int> v;
        Node* cur = root;
        Node* prev = nullptr;

        v.reserve(100);
        while (cur || !st.empty())
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }

            Node* top = st.top();
            if (!top->right || top->right == prev)
            {
                v.push_back(top->val);
                st.pop();

                prev = top;
            }
            else
            {
                cur = top->right;
            }
        }

        return v;
    }

    string tree2str(TreeNode* root)
    {
        string s;

        _tree2str(root, s);

        return s;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    {
        int index = 0;

        return _buildTree2(preorder, inorder, index, 0, preorder.size() - 1);
    }

    Node* _buildTree2(const vector<int>& pre, const vector<int>& in, int& index, int inbeg, int inend)
    {
        if (index >= (int)pre.size())
            return nullptr;

        int rooti = inbeg;
        while (rooti <= inend && in[rooti] != pre[index])
        {
            ++rooti;
        }

        Node* root = new Node(pre[index]);
        if (inbeg <= rooti - 1)
            root->left = _buildTree2(pre, in, ++index, inbeg, rooti - 1);

        if (rooti + 1 <= inend)
            root->right = _buildTree2(pre, in, ++index, rooti + 1, inend);

        return root;
    }

    void _InOrder(Node* cur, Node*& prev)
    {
        if (!cur)
            return;

        _InOrder(cur->left, prev);
        cur->left = prev;
        if (prev)
            prev->right = cur;
        prev = cur;
        _InOrder(cur->right, prev);
    }

    void _tree2str(Node* root, string& s)
    {
        if (!root)
            return;

        s += to_string(root->val);

        if (!root->left && !root->right)
            return;
        else if (root->left && root->right)
        {
            s += '(';
            _tree2str(root->left, s);
            s += ')';

            s += '(';
            _tree2str(root->right, s);
            s += ')';
        }
        else if (root->left)
        {
            s += '(';
            _tree2str(root->left, s);
            s += ')';
        }
        else
        {
            s += "()";

            s += '(';
            _tree2str(root->right, s);
            s += ')';
        }
    }

    Node* _buildTree1(const vector<int>& pre, const vector<int>& in, int& index, int inbeg, int inend)
    {
        if (inbeg > inend)
            return nullptr;

        int rooti = inbeg;
        while (rooti <= inend && in[rooti] != pre[index])
        {
            ++rooti;
        }

        Node* root = new Node(pre[index++]);
        root->left = _buildTree1(pre, in, index, inbeg, rooti - 1);
        root->right = _buildTree1(pre, in, index, rooti + 1, inend);

        return root;
    }
};

bool is(const string& s)
{
    if (s[0] == s[2] && (s[3]-s[1] == 1))
        return true;
    return false;
}

void Test1()
{
    string s;
    const int n = 5;

    int cnt = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> s;
        if (is(s))
            ++cnt;
    }
    cout << cnt << endl;
}

void Test2()
{
    string S, T;
    vector<int> cnts(28);
    vector<int> cntt(28);

    cin >> S >> T;
    for (const auto& x : S)
    {
        ++cnts[x - 'A'];
    }
    for (const auto& x : T)
    {
        ++cntt[x - 'A'];
    }

    int ans = 0;
    if (cnts != cntt)
    {
        for (int i = 0; i < 28; ++i)
        {
            while (cntt[i] && cnts[i] < cntt[i])
            {
                ++ans;
                ++cnts[i];
            }
        }
    }
    cout << ans << endl;
}

void Test3()
{
    /*vector<int> pre{ 3, 9, 20, 15, 7 };
    vector<int> in{9, 3, 15, 20, 7};*/

    vector<int> pre({ 1, 2 });
    vector<int> in({ 1, 2 });

    Solution().buildTree(pre, in);
}

int main()
{
    Test3();

    return 0;
}